#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAXSIZE 20

/**
 * 数组初始化（生成随机数）
 * @param A
 * @param length
 */
void ArrayInit(int A[], int length) {
    srand(time(NULL));  // 初始化随机种子
    for (int i = 0; i < length && i < MAXSIZE; ++i) {
        A[i] = rand() % 100;
    }
    A[0] = 0;   // 0号位置不存元素，仅做暂存
}

/**
 * 打印数组
 * @param A
 * @param length
 */
void ArrayPrint(int A[], int length) {
    for (int i = 0; i < length; ++i) {
        printf("%3d ", A[i]);
    }
    printf("\n");
}

/**
 * 希尔排序
 * @param A
 * @param length
 */
void ShellSort(int A[], int n) {
    int d, i, j;
    // A[0]只是暂存单元，不是哨兵，j<=0时插入位置已到
    for (d = n/2; d >= 1; d = d/2) {    // 步长
        for (i = d+1; i <= n; ++i) {    // 扫描后半段
            if (A[i] < A[i-d]) {        // 如果后面的元素小于前面的，则需要将后面的元素插入到前面的有序序列中
                A[0] = A[i];            // 暂存目标元素
                for (j = i-d; j > 0 && A[0] < A[j]; j = j-d) {
                    A[j+d] = A[j];      // 序列后移，查找需要插入的位置
                }
                // 跳出循环时，j = 目标位置-d
                A[j+d] = A[0];          // 插入目标元素
            }
        }
    }
}


int main() {
    printf("Hello, ShellSort!\n");

    int A[MAXSIZE];         // 定义数组
    int length = 10;        // 设置使用的长度

    // 初始化数组生成随机数
    // 0号位置用于暂存元素
    ArrayInit(A, length+1);
    ArrayPrint(A+1, length);

    // 希尔排序
    ShellSort(A, length);
    ArrayPrint(A+1, length);

}